/*
提交链接：https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/564516314
2616. 最小化数对的最大差值-中等
完成日期：2024/9/13
二分搜索
*/

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(), nums.end()); // 先对数组进行排序
        int left = 0, right = nums.back() - nums.front();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFormPairsWithMaxDiff(nums, p, mid)) {
                right = mid; // 尝试更小的差值
            } else {
                left = mid + 1; // 增大差值
            }
        }
        
        return left;
    }
private:
    bool canFormPairsWithMaxDiff(const vector<int>& nums, int p, int maxDiff) {
        int count = 0;
        int i = 0;
        int n = nums.size();
        while (i < n - 1) {
            if (nums[i + 1] - nums[i] <= maxDiff) {
                count++;
                i += 2; // 使用这对下标
            } else {
                i++; // 试下一个可能的下标对
            }
            if (count >= p) {
                return true;
            }
        }
        return count >= p;
    }
};